// syntax
//
// alternation  = series ('|' series)*
// series       = (pattern quantifier?)+
// pattern      =
//                anchor
//              / any
//              / element
//              / group
//              / set
// group        =
//                '(' flag? alternation ')'
//              / '(?' option+ (':' alternation)? ')'
//              / '(<' name '>' alternation ')'
// reference    = '\g<' (name / ('-'/'+')? DIGIT+ )'>'
// option       = '-'? ('i' / 'm')
// flag         = '!' / '&' / ':' / '?'
// name         = ALPHA ('-'? ALNUM)*
// reference    = name / '-'? DIGIT+
//
//
// set          = '[' '^'? (element / range)']'
// range        = codepoint '-' codepoint
//
// element      =
//                boundary
//              / codepoint
//              / binary
//              / general
//              / matcher
//              / native
//              / posix
//              / reference
//              / script
//
// anchor       = '$' / '^' / boundary
// boundary     = '\' ('B' / 'b' / 'E'/ 'e')
// matcher      = ('\' DIGIT)+
// posix        = '[:' ALPHA+ ':]'
//

import {
  zFlag
} from './zflag'

import {
  trieIt,
  trieMerge,
  trieSearch
} from './trie'

import {
  POSIX,
  BinaryProperties,
  Control,
  GeneralCategory,
  Scripts
} from '../ast/regex-aliases'

import {
  toHex,
  hexValue,
  isAlpha,
  isDigit,
  isHex,
  isOctal,
  decimal,
} from './helper'

let iota = 0

const
  fail = 1,
  GroupHead = [
    '(',  // (subexp)        capturing group
    '(!', // (!look)subexp   not-predicate
    '(&', // (&look)subexp   and-predicate
    '(:', // (:subexp)       non-capturing group
    '(<', // (<name>subexp)  define named ([[:alpha:]](-?[[:alnum:]])*) group
    '(?', // (?Options) / (?Options:subexp) -ims
  ],
  GroupData = ['', '!', '&', ':', '<', '?'],
  Reference = [
    '\\g<', // group reference \<n>, \<-n>, \<name>
  ],
  Sets    = ['[', '[^'],
  Tap     = ['\\O', '\\P', '\\U', '\\o', '\\p', '\\u'],
  Options = [
    '-',  // xyz (set) or -xyz (clear) or xy-z (set xy, clear z)
    'i',  // ignore case ([a-z] ≡ [A-Z])
    'm',  // multi-line (dot (.) also matches newline [\n])
  ].map(s => s.charCodeAt(0)),

  Quantifier = [
    '*',   // zero or more x, prefer more
    '*?',  // zero or more x, prefer fewer
    '+',   // one or more x, prefer more
    '+?',  // one or more x, prefer fewer
    '?',   // zero or one x, prefer one
    '??',  // zero or one x, prefer zero
    '{',   // {n,m} / {n,m}? / {n,} / {n,}? / {n} / {n}?
  ],
  QuantifierValues = Quantifier.map(
    (s) => Array.from(s).map(s => s.charCodeAt(0))
  ),
  Anchors = [
    '$',    // end of the line
    '\\B',  // non-word boundary
    '\\E',  // end of string, or before newline at the end
    '\\G',  // where the current search attempt begins
    '\\b',  // word boundary
    '\\e',  // end of string
    '^',    // beginning of the line
  ],
  AnchorsData = ['$', 'B', 'E', 'G', 'b', 'e', '^'],
  Any = [
    '.',    // [^\n\v\f\r\x85\u{2028}\u{2029}]
  ],
  Characters = [
    '\\',
    '\\f',  // form feed            0x0C
    '\\n',  // newline (line feed)  0x0A
    '\\r',  // carriage return      0x0D
    '\\t',  // horizontal tab       0x09
    '\\v',  // vertical tab         0x0B
  ],
  CharactersData = [
    0, 0x0C, 0x0A, 0x0D, 0x09, 0x0B
  ],
  Codepoints = [
    '\\o{', // wide octal char               \o{17777777777}
    '\\u{', // wide hexadecimal char         \u{7HHHHHHH}
    '\\x',  // hexadecimal char              \xHH
    '\\O{', // negative wide octal char
    '\\U{', // negative wide hexadecimal char
    '\\X',  // negative hexadecimal char
  ],
  ControlMark = [
    '\\c',  // control char abbreviation      \cXXX or \c-XX
    '\\C',  // non-control char abbreviation
  ],
  Native = [
    '\\a',  // alphabetic char         [A-Za-z]
    '\\d',  // decimal digit char      [0-9]
    '\\h',  // hexadecimal digit char  [0-9a-fA-F]
    '\\l',  // Unicode linebreak       [\f\v\x85\p{Zl}\p{Zp}]|\r\n?
    '\\s',  // Unicode whitespace      [\p{WSpace}\p{Pattern_White_Space}]
    '\\w',  // word character          [\p{ID_Continue}]
    '\\A',  // non-alphabetic char
    '\\D',  // non-decimal-digit char
    '\\H',  // non-hexdigit char
    '\\L',  // negative Unicode linebreak
    '\\S',  // non-whitespace char
    '\\W',  // non-word char
  ],
  NativeData = ['a', 'd', 'h', 'l', 's', 'w'],
  NativeMax = NativeData.length,
  PropertyHead = [
    '\\p{', // \p{property-name}
    '\\P{', // \P{property-name} negative
  ],
  Matcher = [
    '\\0',
    '\\1',
    '\\2',
    '\\3',
    '\\4',
    '\\5',
    '\\6',
    '\\7',
    '\\8',
    '\\9',
  ],
  // keep order
  elements = [0],
  aliases  = [0],
  controls = [0],

  alternation     = iota = 0,
  anchor          = merge(Anchors, ++iota, elements),
  any             = merge(Any, ++iota, elements),
  binary          = merge(BinaryProperties.map(s => s + '}'), ++iota, aliases),
  codepoint       = ++iota,
  general         = merge(GeneralCategory.map(s => s + '}'), ++iota, aliases),
  group           = merge(GroupHead, ++iota, elements),
  matcher         = merge(Matcher, ++iota, elements),
  native          = merge(Native, ++iota, elements),
  negative        = ++iota,
  posix           = merge(POSIX.map(s => s + ':]'), ++iota, aliases),
  quantifier      = merge(Quantifier, ++iota, elements),
  range           = ++iota, // -
  reference       = merge(Reference, ++iota, elements),
  script          = merge(Scripts.map(s => s + '}'), ++iota, aliases),
  series          = ++iota,
  set             = merge(Sets, ++iota, elements), // [xyz], [^xyz]

  // transform

  tap             = merge(Tap, ++iota, elements),
  tCodepoints     = merge(Codepoints, ++iota, elements),    // codepoint
  tControl        = merge(ControlMark, ++iota, elements),   // codepoint
  tCharacter      = merge(Characters, ++iota, elements),    // codepoint
  tProperty       = merge(PropertyHead, ++iota, elements),  // binary / general / script

  after = Array(iota) // matched

Control.forEach((word, i) => {
  if (i & 1) return
  if (word.length === 2)
    word = '-' + word
  else if (word.length !== 3)
    throw Error('incorrect Control Name Aliases')
  trieMerge(trieIt(word, i + 1), controls)
})

after[anchor] = function (lex, cp, parent, index) {
  parent.body.push(node(anchor, AnchorsData[index]))
}
after[any] = function (lex, cp, parent) {
  parent.body.push(
    parent.sign === set
    && node(codepoint, 0x2E)
    || node(any, 0x2E)
  )
}

after[group] = function (lex, cp, parent, index) {
  if (parent.sign === set)
    return lex.unexpected()

  let n = node(group, GroupData[index], [])

  parent.body.push(n)

  if (n.data === '?') {
    while (Options.includes(cp)) {
      n.data += String.fromCharCode(cp)
      cp = lex.step()
    }
    if (n.data.length === 1) return lex.unexpected()
    if (cp === 0x29) {
      lex.step()
      return
    }
    // :
    if (cp !== 0x3A) return lex.unexpected()
    cp = lex.step()
  } else if (n.data === '<') {
    if (!isAlpha(cp)) return lex.unexpected()
    n.data = nameify(lex, cp)
    if (lex.cp !== 0x3E || !n.data)
      return lex.unexpected()
    cp = lex.step()
  }

  if (enter(lex, cp, n, 0x29)) return fail

  if (!n.body.length)
    return lex.fail('invalid empty group')
}

after[matcher] = function (lex, cp, parent, index) {
  let last = getLast(parent.body)
  if (last && last.sign === matcher)
    last.data = last.data * 10 + index
  else
    parent.body.push(node(matcher, index))
}

after[native] = function (lex, cp, parent, index) {
  parent.body.push(
    negify(
      index >= NativeMax,
      node(native, NativeData[index % NativeMax])
    )
  )
}
after[quantifier] = function (lex, cp, parent, index) {
  let
    last = getLast(parent.body),
    cps = QuantifierValues[index]

  if (parent.sign === set || !last && cps.length === 1) {
    cps.forEach(
      cp => parent.body.push(node(codepoint, cp))
    )
    return
  }

  if (!last) {
    parent.body.push(node(codepoint, cps[0]))
    parent.body.push(node(quantifier, '?'))
    return
  }

  if (last.sign === quantifier)
    return lex.fail('bad pattern', cps.length + 1)

  let n = node(quantifier, Quantifier[index])

  if (n.data === '{') {
    n.body = []
    n.data = '='
    if (!isDigit(cp)) return lex.unexpected()
    n.body.push(node(quantifier, decimal(lex, cp)))
    if (lex.cp === 0x2C) {
      if (!isDigit(lex.step()))
        n.body.push(node(quantifier, -1))
      else
        n.body.push(node(quantifier, decimal(lex, lex.cp)))
    }

    if (lex.cp !== 0x7D) return lex.unexpected()
    if (lex.step() === 0x3F) {
      lex.step()
      n.data += '?'
    }
  }
  parent.body.push(n)
}

after[reference] = function (lex, cp, parent) {
  let n = node(reference, 0)
  if (isAlpha(cp)) {
    n.data = nameify(lex, cp)
    if (!n.data) return lex.unexpected()
    cp = lex.cp
  } else if (cp === 0x2D || isDigit(cp)) {
    let neg = cp === 0x2D
    if (neg) cp = lex.step()
    while (isDigit(cp)) {
      n.data = n.data * 10 + cp - 0x30
      cp = lex.step()
    }
    if (n.data === 0) return lex.unexpected()
    if (neg) n.data = -n.data
  }

  if (cp !== 0x3E) return lex.unexpected()

  cp = lex.step()
  parent.body.push(n)
}

after[set] = function (lex, cp, parent, index) {
  let hyphen = -1, n, non = index === 1
  if (!non && cp === 0x3A)
    return posixEnter(lex, lex.step(), parent)

  n = node(set, 0, [])

  while (lex.cp !== 0x5D) {
    cp = lex.cp

    if (hyphen === n.body.length)
      hyphen = rangeify(n.body)

    if (cp === 0x5C) { // \
      if (invoke(lex, cp, n, elements)) return fail
      continue
    }

    if (cp === 0x5B) { // [:
      if (lex.step() !== 0x3A)
        n.body.push(node(codepoint, 0x5B))
      else if (posixEnter(lex, lex.step(), n))
        return fail
      continue
    }

    if (cp === 0x2D) {// -
      let last = getLast(n.body)
      if (last && last.sign === codepoint)
        hyphen = n.body.length + 2
    } else if (invalid(cp))
      return lex.unexpected()

    n.body.push(node(codepoint, cp))

    lex.step()
  }

  if (hyphen === n.body.length)
    rangeify(n.body)
  else if (!n.body.length)
    return lex.fail('invalid empty set')

  lex.step()
  parent.body.push(negify(non, n))
}

// transform
after[tap] = function (lex) {
  return lex.unexpected()
}

after[tCodepoints] = function (lex, cp, parent, index) {
  let non = index > 2, n = node(codepoint, 0)

  index -= non && 3 || 0

  if (index === 2) {
    if (!isHex(cp) || !isHex(lex.step()))
      return lex.unexpected()
    n.data = hexValue(cp) * 16 + hexValue(lex.cp)
  } else {
    let c = 1
    if (index === 1)
      while (true) {
        let v = hexValue(cp)
        if (v < 0) break
        n.data = n.data * 16 + v
        cp = lex.step()
        c++
      }
    else
      while (isOctal(cp)) {
        n.data = n.data * 8 + cp - 0x30
        cp = lex.step()
        c++
      }

    if (cp !== 0x7D) return lex.unexpected()

    if (n.data > 0x10FFFF)
      return lex.fail(
        'invalid U+' + toHex(n.data), c
      )
  }
  lex.step()
  parent.body.push(
    negify(non, n)
  )
}

after[tControl] = function (lex, cp, parent, index) {
  let non = index === 1
  index = trieSearch(controls, lex, cp)
  if (!index) return lex.unexpected()
  parent.body.push(
    negify(non, node(codepoint, Control[index]))
  )
}

after[tCharacter] = function (lex, cp, parent, index) {
  if (index)
    cp = CharactersData[index]
  else if (invalid(cp))
    return lex.unexpected()
  else
    lex.step()

  parent.body.push(
    node(codepoint, cp)
  )
}

after[tProperty] = function (lex, cp, parent, index) {
  // binary / general / script
  let
    [sign, idx] = match(aliases, lex, cp),
    array =
         sign === binary && BinaryProperties
      || sign === general && GeneralCategory
      || sign === script && Scripts
      || null

  if (!array) return lex.unexpected()

  parent.body.push(
    negify(index === 1, node(sign, array[idx - (idx & 1)]))
  )
}

aliases
after[binary] =
after[general] =
after[posix] =
after[script] = function (lex) {
  return lex.unexpected()
}

// iota

after[alternation] = function (lex, cp, parent) {
  if (parent.sign === set)
    return lex.unexpected()
  parent.body.push(node(codepoint, cp))
  lex.step()
}

after[codepoint] =
after[negative] =
after[range] =
after[series] = function (lex) {
  return lex.unexpected()
}

function posixEnter (lex, cp, parent) {
  let non = cp === 0x5E // ^
  if (non) lex.step()
  let [sign, index] = match(aliases, lex, lex.cp)
  if (sign !== posix) return lex.unexpected()
  parent.body.push(
    negify(non, node(posix, POSIX[index]))
  )
}

function getLast (body) {
  return body.length
      && body[body.length - 1]
      || null
}

function rangeify (body) {
  let last = getLast(body)
  if (last.sign === codepoint) {
    body.pop()
    body.pop()
    let i = body.length - 1
    body[i] = node(range, 0, [body[i], last])
  }
  return  0
}

function negify (non, n) {
  return non && node(negative, n) || n
}

function nameify (lex, cp) {
  let start = lex.offset() - 1
  while (isAlpha(cp) || isDigit(cp)) {
    cp = lex.step()
    while (cp === 0x2D) {
      cp = lex.step()
      if (!isAlpha(cp) && !isDigit(cp)) return ''
      cp = lex.step()
    }
  }
  return lex.substring(start, lex.offset() - 1)
}

function node (sign, data, body) {
  return body
      && {sign, data, body}
      || {sign, data}
}

function merge (a, iota, trie) {
  let prev = ''
  a.forEach((word, index) => {
    if (word !== prev)
      trieMerge(trieIt(word, (iota << 16) + index), trie)
    prev = word
  })
  return iota
}

function match (trie, lex, cp) {
  let sign  = trieSearch(trie, lex, cp)
  return [sign >> 16, sign & 0xFFFF ]
}

function invalid (cp) {
  return zFlag(cp) === 0
}

function invoke (lex, cp, parent, trie) {
  let
    pos = lex.offset(),
    [sign, index] = match(trie, lex, cp)
  if (!sign && (pos !== lex.offset() || invalid(cp)))
    return lex.unexpected()

  return after[sign](lex, lex.cp, parent, index)
}

function enter (lex, cp, n, stop) {
  let alt = [], body = n.body
  if (cp === 0x7C) {
    body.push(node(codepoint, cp))
    cp = lex.step()
  }
  while (cp !== stop) {
    if (cp !== 0x7C) {
      if (invoke(lex, cp, n, elements)) return fail
      cp = lex.cp
      continue
    }
    // |
    cp = lex.step()

    if (cp === stop) {
      body.push(node(codepoint, 0x7C))
      break
    }

    alt.push(
      body.length === 1 && body[0]
      || node(series, 0, body)
    )
    body = n.body = []
    if (cp === 0x7C) {
      body.push(node(codepoint, cp))
      cp = lex.step()
    }
  }
  lex.step()
  if (alt.length) {
    if (body.length)
      alt.push(
        body.length === 1 && body[0]
        || node(series, 0, body)
      )
    n.body = [node(alternation, 0, alt)]
  }
}

export default function (lex, cp, body) {
  let n = node(series, 0, [])
  if (enter(lex, cp, n, 0x2F)) return fail
  body.push(...n.body)
}
